package uba.fi.tda.tp3;

public class Ecentricidad {
	
	// Devuelve el vertice cuya ecentricidad es minima
	public static Resultado calcularEcentricidadMinima(Grafo grafo){
		int ecentricidadMinima = grafo.infinito;
		int indice = -1;
		
		// Calculo la ecentricidad para cada uno de los nodos del grafo
		for(int i = 0; i < grafo.getCantidadVertices() ; i++){
			
			int ecentricidad = calcularEcentricidad(i, grafo);
 
			if (ecentricidad < ecentricidadMinima){
				ecentricidadMinima = ecentricidad;
				indice = i;
			}
		}
		
		if (indice >= 0){
			Resultado resultado = new Resultado();
			resultado.setEcentricidad(ecentricidadMinima);
			resultado.setVertice(grafo.getVertices()[indice]);
			return resultado;
		}
		return null;
	} 
	
	// Devuelve la distancia al nodo mas lejano del nodo cuyo indice es el pasado por parametro
	private static int calcularEcentricidad(int idVerticeInicial,Grafo grafo) {
        
		int ecentricidad = 0;
		
		grafo.inicializarGrafo();
		// Recorro el grafo.
        ColaPrioridad cola = new ColaPrioridad(grafo.getCantidadVertices());
        // Se agrega un Camino con el Vertice inicial, y peso 0.
        cola.encolar(new Camino(grafo.getVertices()[idVerticeInicial], 0));
        grafo.getVertices()[idVerticeInicial].setCosto(0);
        while(!cola.vacia()) {
            Camino camino = (Camino)cola.extraerMinimo();
            Vertice vertice = camino.getDestino();
            if(!vertice.isProcesado()) {
                // Recorremos la lista de adyacencia.
                IteradorLista iterador = vertice.getAdyacentes().getInicio();
                while(!iterador.isNull()) {
                    Arista a = (Arista)(iterador.getDato());
                    Vertice w = a.getVerticeFinal();
                    int costo_v_w = a.getPeso(); // El costo de ir de vertice a w es el peso de la arista.                    
                    if(w.getCosto() > vertice.getCosto() + costo_v_w) {
                        w.setPadre(vertice);
                        w.setCosto(vertice.getCosto() + costo_v_w);
                        if(w.getCosto() > ecentricidad){
                        	ecentricidad = w.getCosto();
                        }
                        cola.encolar(new Camino(w, w.getCosto()));
                    }
                    iterador.next();
                }
                vertice.setProcesado(true);
            }
        }
        return ecentricidad;
	}
}
